package com.sheng.leetcode.year2023.month04.day24;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/04/24
 * <p>
 * 1163. 按字典序排在最后的子串<p>
 * <p>
 * 给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。<p>
 * <p>
 * 示例 1：<p>
 * 输入：s = "abab"<p>
 * 输出："bab"<p>
 * 解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。<p>
 * <p>
 * 示例 2：<p>
 * 输入：s = "leetcode"<p>
 * 输出："tcode"<p>
 * <p>
 * 提示：<p>
 * 1 <= s.length <= 4 * 10^5<p>
 * s 仅含有小写英文字符。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/last-substring-in-lexicographical-order">1163. 按字典序排在最后的子串</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1163 {

    @Test
    public void test01() {
        String s = "abab";
//        String s = "leetcode";
        System.out.println(new Solution().lastSubstring(s));
    }
}

class Solution {
    public String lastSubstring(String s) {
        // 字典序最大的子串，从第一个字符开始，每个字符都得是同序列上最大的，然后一直持续到字符串结束
        int n = s.length();
        // i 指向当前字典序最大的子串的起始位置
        int i = 0;
        // j 指向和 i 进行判断的子串的起始位置，k 记录两个子串当前比较到的位置
        for (int j = 1, k = 0; j + k < n; ) {
            int d = s.charAt(i + k) - s.charAt(j + k);
            if (d == 0) {
                // 相等，说明相同，将 k 加 1，比较两个子串的后一个字符
                ++k;
            } else if (d < 0) {
                // 说明 j 开头的子串更大
                // 更新最大子串的起始位置 i
                i += k + 1;
                // 重置 k
                k = 0;
                // 更新要进行比较的子串 j
                if (i >= j) {
                    j = i + 1;
                }
            } else {
                // 说明 i 开头的子串比 j 开头的更大
                // 更新 j 子串的起始位置
                j += k + 1;
                // 重置 k
                k = 0;
            }
        }
        // 返回 i 所在子串
        return s.substring(i);
//        String index = null;
//        int num = 0;
//        for (int i = 25; i >= 0; i--) {
//            if (s.indexOf(i + 97) != -1) {
//                if (index == null) {
//                    index = (char) (i + 97) + "";
//                }
//                num++;
//            }
//        }
//        if (num == 1) {
//            return s;
//        }
//        List<String> list = new ArrayList<>();
//        int i = n;
//        while (s.lastIndexOf(index, i) != -1) {
//            list.add(s.substring(s.lastIndexOf(index, i)));
//            i = s.lastIndexOf(index, i) - 1;
//        }
//        Collections.sort(list);
//        return list.get(list.size() - 1);
    }
}
